博弈论趣题
问题
有一个二分图,点带点权,分成A集合和B集合。两人轮流选点,每次只能选和上一次有连边的点(第一次从A集合任选),选到一个点把点权,点权为的点不能再选。最后不能选者失败。求一个先手必胜策略或说明先手必败。
结论
先手应该选择一个不一定在最大匹配中的点。即存在一个最大匹配使得该点没有被匹配满。如果这样的点不存在则先手必败。
证明
对于任意一个最大匹配,首先选择一个不在该匹配中的点,对于对手选的每个点,我们都选择在匹配中和它对应的那个点。可以证明对手在任何时候都不能选择不在匹配中的点(否则把所有选过的点连起来是一条增广路,该匹配不是最大匹配),先手必胜。否则,如果先手选择了一个必定在最大匹配中的点,该点点权后最大匹配必然跟着,那么原来的最大匹配去掉了该点和B集合对应的点这组匹配后仍然是最大匹配。此时该对应点就是成为了不一定在最大匹配中的点,按照上面的证明后手必胜。(也可以用归纳法证明)
如何求这样的点
使用网络流求出最大匹配,然后在残余网络上dfs。记超级原点为,超级汇点为,则在一侧的点中,可达的就是不一定在最大匹配中的点。逆命题也成立。一侧同理。
这个方法的证明
对于一侧可达的点,若原图边没有流满显然成立,否则沿着这条回路加流量,变化后的最大流中边就没有流满。
例题(然而并没有地方提交)
小A和小B正在进行一场博弈,规则如下:开始时,有若干个正整数。游戏的第一步中小A先任选一个数删去,之后两个人轮流操作,每次选择一个数并删去。设当前选择的数为,前一个选择的数为,则和中必须有一个质数。无法操作者负。对于给定的初始数集,你需要确定:小A是否有必胜策略?如果有,小A在第一步中可以选择哪些数?
输入第一行为一个正整数;接下来行,每行两个正整数,表示正整数在一开始的数中出现了次。
若小A没有必胜策略,输出-1;否则,升序输出小A第一步可以选择,以确保自己必胜的数。